﻿/*
题目: 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
#define EMPTY "null"
#define SEP "|"

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        // 层序遍历
        string bin;
        if (root == nullptr)    return bin;

        queue<TreeNode*> q;
        q.push(root);
        bin += to_string(root->val) + SEP;

        while (!q.empty()) {
            int sz = q.size();
            while (sz-- > 0) {
                TreeNode* nd = q.front();
                q.pop();

                if (nd->left) {
                    q.push(nd->left);
                    bin += to_string(nd->left->val) + SEP;
                }
                else {
                    bin += EMPTY;
                    bin += SEP;
                }

                if (nd->right) {
                    q.push(nd->right);
                    bin += to_string(nd->right->val) + SEP;
                }
                else {
                    bin += EMPTY;
                    bin += SEP;
                }
            }
        }
        std::cout << bin << std::endl;
        return bin;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string bin) {
        if (bin.size() == 0)   return nullptr;

        int i = 0;
        int end = bin.find(SEP, i);
        int real_end = bin.size() - 1;

        function<string(int&, int&)> next_data = [&bin](int& i, int& end) -> string {
            end = bin.find(SEP, i);
            string str = bin.substr(i, end - i);
            i = end + 1;
            return str;
        };

        TreeNode* root = new TreeNode(stoi(next_data(i, end)));

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int sz = q.size();
            while (sz-- > 0) {
                TreeNode* nd = q.front();
                q.pop();

                // left
                if (end != real_end) {
                    string val = next_data(i, end);
                    if (val == EMPTY)   nd->left = nullptr;
                    else {
                        nd->left = new TreeNode(stoi(val));
                        q.push(nd->left);
                    }
                }
                if (end != real_end) {
                    string val = next_data(i, end);
                    if (val == EMPTY)   nd->right = nullptr;
                    else {
                        nd->right = new TreeNode(stoi(val));
                        q.push(nd->right);
                    }
                }

                if (end == real_end)    return root;
            }
        }

        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
